Methods for estimating the matching (i.e., similarity) between two graphs (e.g., representing two images) are known in the art. One of the methods for estimating the matching is by formulating the matching as an assignment problem between two sets of points, x1i, 1 . . . N1 and x2j, i=1 . . . N2. The term “affinity” as detailed herein below, refers to the similarity or correspondence between two objects. For example, the affinity of two feature points is defined by the similarity between the descriptors of the feature points. Another example is the affinity of two pairs of feature points (i.e., pair-wise affinity), which refers to the similarity between the geometric relations between the points within each pair (i.e., the difference in the distances between the points within each pair). The pair-wise affinity can further incorporate the similarities between the descriptors of the points.
The term “affinity tensor” as detailed herein below refers to a tensor including the affinity score between each of the objects of a first set of objects and each of the objects of a second set of objects. The rank of the tensor (i.e., the number of indices required for defining an entry) is determined according to the number of points of each set which are matched. For example, a pair-wise affinity tensor is a two dimensional matrix, a triple-wise affinity tensor is three dimensional, a quadruple-wise affinity tensor is four dimensional. The term “assignment” as detailed herein below, refers to an assignment of a first object of a first set of objects to a second object of a second set of objects. Each assignment is weighted according to the correspondence (e.g., affinity score) between the first object and the second object. It is noted that a set of assignments between two sets of objects can be subjected to constraints. For example a one-to-one constraint means that each object of the first set can be assigned to not more than a single object of the second set. The term “optimal assignment” as detailed herein below, refers to a set of assignments (e.g., arranged in an assignment vector), which summed value (e.g., summed affinity score) is maximal.
An article (herein below referred to as “the article”) published by Marius Leordeanu and Martial Hebert, and entitled “A Spectral Technique for Correspondence Problems Using Pair-wise Constraints”, describes such a method. The article describes a method for estimating a matching between two sets of points. The first step is formulating the matching as an assignment problem (i.e., trying to find the optimal assignment). The next step is defining an assignment indicator vector—Z (i.e., which an optimum thereof is the sought solution—the optimal assignment). An example of the assignment indicator vector Z is given by the following formula:
                    z        =                              (                                                                                                      1                      ︸                                                                                      i                        =                        1                                            ,                                              j                        =                        1                                                                                                              0                                                  0                                                  |                                                  0                                                                                            1                      ︸                                                                                      i                        =                        2                                            ,                                              j                        =                        2                                                                                                              0                                                  |                                                                                            1                      ︸                                                                                      i                        =                        3                                            ,                                              j                        =                        1                                                                                                              0                                                  0                                                      )                    T                                    (        1        )            where zij is the j'th element in the i'th sub-segment of the vector Z. zij=1, implies that x1i corresponds to x2j (i.e., the affinity score of x1i and x2j is above a predetermined value).
It is noted that the assignment indicator vector Z corresponds to an assignment which is subjected to a one-to-one constraint. Every sub-segment of the assignment vector Z contains, at most, a single element with a value of 1 and a plurality of elements with a value of 0. In case a point of x1i matches no point of x2j, all the elements of the respective sub-segment of Z have a zero value. It is further noted that a one-to-one constraint is typical when matching points representing two physical objects since no physical point on one object can be matched (i.e., assigned or corresponded) to more than a single point on another object.
In order to estimate the assignment indicator vector Z, the next step is determining a pair-wise affinity matrix—A, such that Aij; is the affinity of two assignments
                                                                        A                                                      (                                          i                      +                                              i                        ′                                                              )                                    ⁢                                      (                                          j                      +                                              j                        ′                                                              )                                                              =                              A                ⁡                                  (                                                                                    x                        1                        i                                            →                                              x                        2                        j                                                              ,                                                                  x                        1                                                  i                          ′                                                                    →                                              x                        2                                                  j                          ′                                                                                                      )                                                                                                        =                              exp                -                                  (                                                                                    (                                                                                                                                                                        x                                1                                i                                                            -                                                              x                                1                                                                  i                                  ′                                                                                                                                                                          -                                                                                                                                                x                                1                                j                                                            -                                                              x                                1                                                                  j                                  ′                                                                                                                                                                                                )                                            2                                                              σ                      2                                                        )                                                                                                                        =                                  exp                  -                                      (                                                                                            (                                                                                    d                                                              ii                                ′                                                                                      -                                                          d                                                              jj                                ′                                                                                                              )                                                2                                                                    σ                        2                                                              )                                                              ,                                                          (        2        )            where σ is a predefined constant, dii′ is defined as a distance between x1i and x1i′, while djj′ is a distance between x2j and x2j′. Hence, σ is a scale measure that determines the similarity of distances. The next step is maximizing the following quadratic score function:
                                          z            *                    =                                                    arg                ⁢                                                                  ⁢                max                            z                        ⁢                                                  ⁢                          z              T                        ⁢            Az                          ,                  z          ∈                                    {                              0                ,                1                            }                        .                                              (        3        )            
Since the solution of equation (3) is known to be np-hard, the next step is applying spectral relaxation and solving the following equation:
                                          p            *                    =                      max            ⁢                                                                                            ⁢                arg                            z                        ⁢                                                            p                  T                                ⁢                Ap                                                              p                  T                                ⁢                p                                                    ,                  p          ∈                                  .                                              (        4        )            Equation (4) is solved by the eigendecomposition of affinity matrix A. where p*=φ0, φ0 being the eigenvector corresponding to the leading eigenvalue. z* is then recovered be a discretization of p* by the following steps as detailed herein below.
The first step is reducing the size of affinity matrix A. The affinity matrix A is of size N1*N2×N1*N2 since each of the points of x1i is assigned to each of the points of x2j, and each of the assignments is matched with every assignment. Furthermore, all the entries of the primary diagonal of affinity matrix A are of value 1 as these entries represent a matching score between an assignment and itself. It is noted that, when possible, application specific information about tentative correspondences between a point of the first set X1 and a point of the second set X2 is employed for reducing the possible correspondences (i.e., possible assignments).
For example, in case each of the points represents a feature point of an image, the local descriptor of each feature point is employed for ruling out possible assignments in advance (i.e., prior to calculating the value of the assignments). In this manner, the number of possible assignments can vary from point to point (e.g., a first point of the first set of points is assigned to three points of the second set while a second point of the first set is assigned to seven points of the second set). However, for the sake of simplicity of discussion, the number of considered possible correspondences for each point in the set X1 is K, where K≦N2. In this case the size of the affinity matrix is (N1*K)×(N1*K)
The next step is reshaping the relaxed eigenvector p* into matrix of N1×K, where N1 is the number of points in the first set and K is the number of possible correspondent points (i.e., per point in the first set) in the second set of points (i.e., in case K is smaller than N2, the matching score refers to partial matching).
The following step is choosing the maximal value of p*, and marking the corresponding entry in z*(i,j) as one. This step is repeated in iterations over p*. In order to enforce an assignment one-to-one constraint, the next step is marking other possible correspondences involving i or j as null (i.e., impossible assignment). The process continues until all of the entries of p* are marked as null. The spectral similarity measure between the sets x1 and x2 is given by the scalar:Ψ(x1,x2)=zTAz,zε{0,1}.   (5)